home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / etc / RCS / ndbm.c,v < prev    next >
Text File  |  1989-05-18  |  12KB  |  635 lines
  1. head     1.6;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 1.6
  10. date     89.05.18.17.11.35;  author rab;  state Exp;
  11. branches ;
  12. next     1.5;
  13.  
  14. 1.5
  15. date     88.07.29.18.28.33;  author ouster;  state Exp;
  16. branches ;
  17. next     1.4;
  18.  
  19. 1.4
  20. date     88.07.25.13.26.38;  author ouster;  state Exp;
  21. branches ;
  22. next     1.3;
  23.  
  24. 1.3
  25. date     88.07.25.13.09.30;  author ouster;  state Exp;
  26. branches ;
  27. next     1.2;
  28.  
  29. 1.2
  30. date     88.07.25.10.45.50;  author ouster;  state Exp;
  31. branches ;
  32. next     1.1;
  33.  
  34. 1.1
  35. date     88.06.27.15.35.40;  author ouster;  state Exp;
  36. branches ;
  37. next     ;
  38.  
  39.  
  40. desc
  41. @@
  42.  
  43.  
  44. 1.6
  45. log
  46. @Added forward declarations for static functions.
  47. @
  48. text
  49. @/*
  50.  * Copyright (c) 1983 Regents of the University of California.
  51.  * All rights reserved.  The Berkeley software License Agreement
  52.  * specifies the terms and conditions for redistribution.
  53.  */
  54.  
  55. #if defined(LIBC_SCCS) && !defined(lint)
  56. static char sccsid[] = "@@(#)ndbm.c    5.4 (Berkeley) 9/4/87";
  57. #endif LIBC_SCCS and not lint
  58.  
  59. #include <sys/types.h>
  60. #include <sys/stat.h>
  61. #include <sys/file.h>
  62. #include <stdio.h>
  63. #include <errno.h>
  64. #include <ndbm.h>
  65. #include <stdlib.h>
  66. #include <string.h>
  67.  
  68. #define BYTESIZ 8
  69. #undef setbit
  70.  
  71. static  datum makdatum();
  72. static  long dcalchash();
  73. static  int dbm_access();
  74. static  int getbit();
  75. static  int setbit();
  76. static  int finddatum();
  77. static  int delitem();
  78. static  int additem();
  79.  
  80. extern  int errno;
  81. extern    long lseek();
  82.  
  83.     /* VARARGS2 */
  84. DBM *
  85. dbm_open(file, flags, mode)
  86.     char *file;
  87.     int flags, mode;
  88. {
  89.     struct stat statb;
  90.     register DBM *db;
  91.  
  92.     if ((db = (DBM *)malloc(sizeof *db)) == 0) {
  93.         errno = ENOMEM;
  94.         return ((DBM *)0);
  95.     }
  96.     db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0;
  97.     if ((flags & 03) == O_WRONLY)
  98.         flags = (flags & ~03) | O_RDWR;
  99.     strcpy(db->dbm_pagbuf, file);
  100.     strcat(db->dbm_pagbuf, ".pag");
  101.     db->dbm_pagf = open(db->dbm_pagbuf, flags, mode);
  102.     if (db->dbm_pagf < 0)
  103.         goto bad;
  104.     strcpy(db->dbm_pagbuf, file);
  105.     strcat(db->dbm_pagbuf, ".dir");
  106.     db->dbm_dirf = open(db->dbm_pagbuf, flags, mode);
  107.     if (db->dbm_dirf < 0)
  108.         goto bad1;
  109.     fstat(db->dbm_dirf, &statb);
  110.     db->dbm_maxbno = statb.st_size*BYTESIZ-1;
  111.     db->dbm_pagbno = db->dbm_dirbno = -1;
  112.     return (db);
  113. bad1:
  114.     (void) close(db->dbm_pagf);
  115. bad:
  116.     free((char *)db);
  117.     return ((DBM *)0);
  118. }
  119.  
  120. void
  121. dbm_close(db)
  122.     DBM *db;
  123. {
  124.  
  125.     (void) close(db->dbm_dirf);
  126.     (void) close(db->dbm_pagf);
  127.     free((char *)db);
  128. }
  129.  
  130. long
  131. dbm_forder(db, key)
  132.     register DBM *db;
  133.     datum key;
  134. {
  135.     long hash;
  136.  
  137.     hash = dcalchash(key);
  138.     for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
  139.         db->dbm_blkno = hash & db->dbm_hmask;
  140.         db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
  141.         if (getbit(db) == 0)
  142.             break;
  143.     }
  144.     return (db->dbm_blkno);
  145. }
  146.  
  147. datum
  148. dbm_fetch(db, key)
  149.     register DBM *db;
  150.     datum key;
  151. {
  152.     register i;
  153.     datum item;
  154.  
  155.     if (dbm_error(db))
  156.         goto err;
  157.     dbm_access(db, dcalchash(key));
  158.     if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
  159.         item = makdatum(db->dbm_pagbuf, i+1);
  160.         if (item.dptr != NULL)
  161.             return (item);
  162.     }
  163. err:
  164.     item.dptr = NULL;
  165.     item.dsize = 0;
  166.     return (item);
  167. }
  168.  
  169. dbm_delete(db, key)
  170.     register DBM *db;
  171.     datum key;
  172. {
  173.     register i;
  174.  
  175.     if (dbm_error(db))
  176.         return (-1);
  177.     if (dbm_rdonly(db)) {
  178.         errno = EPERM;
  179.         return (-1);
  180.     }
  181.     dbm_access(db, dcalchash(key));
  182.     if ((i = finddatum(db->dbm_pagbuf, key)) < 0)
  183.         return (-1);
  184.     if (!delitem(db->dbm_pagbuf, i))
  185.         goto err;
  186.     db->dbm_pagbno = db->dbm_blkno;
  187.     (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
  188.     if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
  189.     err:
  190.         db->dbm_flags |= _DBM_IOERR;
  191.         return (-1);
  192.     }
  193.     return (0);
  194. }
  195.  
  196. dbm_store(db, key, dat, replace)
  197.     register DBM *db;
  198.     datum key, dat;
  199.     int replace;
  200. {
  201.     register i;
  202.     datum item, item1;
  203.     char ovfbuf[PBLKSIZ];
  204.  
  205.     if (dbm_error(db))
  206.         return (-1);
  207.     if (dbm_rdonly(db)) {
  208.         errno = EPERM;
  209.         return (-1);
  210.     }
  211. loop:
  212.     dbm_access(db, dcalchash(key));
  213.     if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
  214.         if (!replace)
  215.             return (1);
  216.         if (!delitem(db->dbm_pagbuf, i)) {
  217.             db->dbm_flags |= _DBM_IOERR;
  218.             return (-1);
  219.         }
  220.     }
  221.     if (!additem(db->dbm_pagbuf, key, dat))
  222.         goto split;
  223.     db->dbm_pagbno = db->dbm_blkno;
  224.     (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
  225.     if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
  226.         db->dbm_flags |= _DBM_IOERR;
  227.         return (-1);
  228.     }
  229.     return (0);
  230.  
  231. split:
  232.     if (key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ) {
  233.         db->dbm_flags |= _DBM_IOERR;
  234.         errno = ENOSPC;
  235.         return (-1);
  236.     }
  237.     bzero(ovfbuf, PBLKSIZ);
  238.     for (i=0;;) {
  239.         item = makdatum(db->dbm_pagbuf, i);
  240.         if (item.dptr == NULL)
  241.             break;
  242.         if (dcalchash(item) & (db->dbm_hmask+1)) {
  243.             item1 = makdatum(db->dbm_pagbuf, i+1);
  244.             if (item1.dptr == NULL) {
  245.                 fprintf(stderr, "ndbm: split not paired\n");
  246.                 db->dbm_flags |= _DBM_IOERR;
  247.                 break;
  248.             }
  249.             if (!additem(ovfbuf, item, item1) ||
  250.                 !delitem(db->dbm_pagbuf, i)) {
  251.                 db->dbm_flags |= _DBM_IOERR;
  252.                 return (-1);
  253.             }
  254.             continue;
  255.         }
  256.         i += 2;
  257.     }
  258.     db->dbm_pagbno = db->dbm_blkno;
  259.     (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
  260.     if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
  261.         db->dbm_flags |= _DBM_IOERR;
  262.         return (-1);
  263.     }
  264.     (void) lseek(db->dbm_pagf, (db->dbm_blkno+db->dbm_hmask+1)*PBLKSIZ, L_SET);
  265.     if (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ) {
  266.         db->dbm_flags |= _DBM_IOERR;
  267.         return (-1);
  268.     }
  269.     setbit(db);
  270.     goto loop;
  271. }
  272.  
  273. datum
  274. dbm_firstkey(db)
  275.     DBM *db;
  276. {
  277.  
  278.     db->dbm_blkptr = 0L;
  279.     db->dbm_keyptr = 0;
  280.     return (dbm_nextkey(db));
  281. }
  282.  
  283. datum
  284. dbm_nextkey(db)
  285.     register DBM *db;
  286. {
  287.     struct stat statb;
  288.     datum item;
  289.  
  290.     if (dbm_error(db) || fstat(db->dbm_pagf, &statb) < 0)
  291.         goto err;
  292.     statb.st_size /= PBLKSIZ;
  293.     for (;;) {
  294.         if (db->dbm_blkptr != db->dbm_pagbno) {
  295.             db->dbm_pagbno = db->dbm_blkptr;
  296.             (void) lseek(db->dbm_pagf, db->dbm_blkptr*PBLKSIZ, L_SET);
  297.             if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
  298.                 bzero(db->dbm_pagbuf, PBLKSIZ);
  299. #ifdef DEBUG
  300.             else if (chkblk(db->dbm_pagbuf) < 0)
  301.                 db->dbm_flags |= _DBM_IOERR;
  302. #endif
  303.         }
  304.         if (((short *)db->dbm_pagbuf)[0] != 0) {
  305.             item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
  306.             if (item.dptr != NULL) {
  307.                 db->dbm_keyptr += 2;
  308.                 return (item);
  309.             }
  310.             db->dbm_keyptr = 0;
  311.         }
  312.         if (++db->dbm_blkptr >= statb.st_size)
  313.             break;
  314.     }
  315. err:
  316.     item.dptr = NULL;
  317.     item.dsize = 0;
  318.     return (item);
  319. }
  320.  
  321. static
  322. dbm_access(db, hash)
  323.     register DBM *db;
  324.     long hash;
  325. {
  326.  
  327.     for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
  328.         db->dbm_blkno = hash & db->dbm_hmask;
  329.         db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
  330.         if (getbit(db) == 0)
  331.             break;
  332.     }
  333.     if (db->dbm_blkno != db->dbm_pagbno) {
  334.         db->dbm_pagbno = db->dbm_blkno;
  335.         (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
  336.         if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
  337.             bzero(db->dbm_pagbuf, PBLKSIZ);
  338. #ifdef DEBUG
  339.         else if (chkblk(db->dbm_pagbuf) < 0)
  340.             db->dbm_flags |= _DBM_IOERR;
  341. #endif
  342.     }
  343. }
  344.  
  345. static
  346. getbit(db)
  347.     register DBM *db;
  348. {
  349.     long bn;
  350.     register b, i, n;
  351.     
  352.  
  353.     if (db->dbm_bitno > db->dbm_maxbno)
  354.         return (0);
  355.     n = db->dbm_bitno % BYTESIZ;
  356.     bn = db->dbm_bitno / BYTESIZ;
  357.     i = bn % DBLKSIZ;
  358.     b = bn / DBLKSIZ;
  359.     if (b != db->dbm_dirbno) {
  360.         db->dbm_dirbno = b;
  361.         (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
  362.         if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
  363.             bzero(db->dbm_dirbuf, DBLKSIZ);
  364.     }
  365.     return (db->dbm_dirbuf[i] & (1<<n));
  366. }
  367.  
  368. static
  369. setbit(db)
  370.     register DBM *db;
  371. {
  372.     long bn;
  373.     register i, n, b;
  374.  
  375.     if (db->dbm_bitno > db->dbm_maxbno)
  376.         db->dbm_maxbno = db->dbm_bitno;
  377.     n = db->dbm_bitno % BYTESIZ;
  378.     bn = db->dbm_bitno / BYTESIZ;
  379.     i = bn % DBLKSIZ;
  380.     b = bn / DBLKSIZ;
  381.     if (b != db->dbm_dirbno) {
  382.         db->dbm_dirbno = b;
  383.         (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
  384.         if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
  385.             bzero(db->dbm_dirbuf, DBLKSIZ);
  386.     }
  387.     db->dbm_dirbuf[i] |= 1<<n;
  388.     db->dbm_dirbno = b;
  389.     (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
  390.     if (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
  391.         db->dbm_flags |= _DBM_IOERR;
  392. }
  393.  
  394. static datum
  395. makdatum(buf, n)
  396.     char buf[PBLKSIZ];
  397. {
  398.     register short *sp;
  399.     register t;
  400.     datum item;
  401.  
  402.     sp = (short *)buf;
  403.     if ((unsigned)n >= sp[0]) {
  404.         item.dptr = NULL;
  405.         item.dsize = 0;
  406.         return (item);
  407.     }
  408.     t = PBLKSIZ;
  409.     if (n > 0)
  410.         t = sp[n];
  411.     item.dptr = buf+sp[n+1];
  412.     item.dsize = t - sp[n+1];
  413.     return (item);
  414. }
  415.  
  416. static
  417. finddatum(buf, item)
  418.     char buf[PBLKSIZ];
  419.     datum item;
  420. {
  421.     register short *sp;
  422.     register int i, n, j;
  423.  
  424.     sp = (short *)buf;
  425.     n = PBLKSIZ;
  426.     for (i=0, j=sp[0]; i<j; i+=2, n = sp[i]) {
  427.         n -= sp[i+1];
  428.         if (n != item.dsize)
  429.             continue;
  430.         if (n == 0 || bcmp(&buf[sp[i+1]], item.dptr, n) == 0)
  431.             return (i);
  432.     }
  433.     return (-1);
  434. }
  435.  
  436. static  int hitab[16]
  437. /* ken's
  438. {
  439.     055,043,036,054,063,014,004,005,
  440.     010,064,077,000,035,027,025,071,
  441. };
  442. */
  443.  = {    61, 57, 53, 49, 45, 41, 37, 33,
  444.     29, 25, 21, 17, 13,  9,  5,  1,
  445. };
  446. static  long hltab[64]
  447.  = {
  448.     06100151277L,06106161736L,06452611562L,05001724107L,
  449.     02614772546L,04120731531L,04665262210L,07347467531L,
  450.     06735253126L,06042345173L,03072226605L,01464164730L,
  451.     03247435524L,07652510057L,01546775256L,05714532133L,
  452.     06173260402L,07517101630L,02431460343L,01743245566L,
  453.     00261675137L,02433103631L,03421772437L,04447707466L,
  454.     04435620103L,03757017115L,03641531772L,06767633246L,
  455.     02673230344L,00260612216L,04133454451L,00615531516L,
  456.     06137717526L,02574116560L,02304023373L,07061702261L,
  457.     05153031405L,05322056705L,07401116734L,06552375715L,
  458.     06165233473L,05311063631L,01212221723L,01052267235L,
  459.     06000615237L,01075222665L,06330216006L,04402355630L,
  460.     01451177262L,02000133436L,06025467062L,07121076461L,
  461.     03123433522L,01010635225L,01716177066L,05161746527L,
  462.     01736635071L,06243505026L,03637211610L,01756474365L,
  463.     04723077174L,03642763134L,05750130273L,03655541561L,
  464. };
  465.  
  466. static long
  467. hashinc(db, hash)
  468.     register DBM *db;
  469.     long hash;
  470. {
  471.     long bit;
  472.  
  473.     hash &= db->dbm_hmask;
  474.     bit = db->dbm_hmask+1;
  475.     for (;;) {
  476.         bit >>= 1;
  477.         if (bit == 0)
  478.             return (0L);
  479.         if ((hash & bit) == 0)
  480.             return (hash | bit);
  481.         hash &= ~bit;
  482.     }
  483. }
  484.  
  485. static long
  486. dcalchash(item)
  487.     datum item;
  488. {
  489.     register int s, c, j;
  490.     register char *cp;
  491.     register long hashl;
  492.     register int hashi;
  493.  
  494.     hashl = 0;
  495.     hashi = 0;
  496.     for (cp = item.dptr, s=item.dsize; --s >= 0; ) {
  497.         c = *cp++;
  498.         for (j=0; j<BYTESIZ; j+=4) {
  499.             hashi += hitab[c&017];
  500.             hashl += hltab[hashi&63];
  501.             c >>= 4;
  502.         }
  503.     }
  504.     return (hashl);
  505. }
  506.  
  507. /*
  508.  * Delete pairs of items (n & n+1).
  509.  */
  510. static
  511. delitem(buf, n)
  512.     char buf[PBLKSIZ];
  513. {
  514.     register short *sp, *sp1;
  515.     register i1, i2;
  516.  
  517.     sp = (short *)buf;
  518.     i2 = sp[0];
  519.     if ((unsigned)n >= i2 || (n & 1))
  520.         return (0);
  521.     if (n == i2-2) {
  522.         sp[0] -= 2;
  523.         return (1);
  524.     }
  525.     i1 = PBLKSIZ;
  526.     if (n > 0)
  527.         i1 = sp[n];
  528.     i1 -= sp[n+2];
  529.     if (i1 > 0) {
  530.         i2 = sp[i2];
  531.         bcopy(&buf[i2], &buf[i2 + i1], sp[n+2] - i2);
  532.     }
  533.     sp[0] -= 2;
  534.     for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
  535.         sp[0] = sp[2] + i1;
  536.     return (1);
  537. }
  538.  
  539. /*
  540.  * Add pairs of items (item & item1).
  541.  */
  542. static
  543. additem(buf, item, item1)
  544.     char buf[PBLKSIZ];
  545.     datum item, item1;
  546. {
  547.     register short *sp;
  548.     register i1, i2;
  549.  
  550.     sp = (short *)buf;
  551.     i1 = PBLKSIZ;
  552.     i2 = sp[0];
  553.     if (i2 > 0)
  554.         i1 = sp[i2];
  555.     i1 -= item.dsize + item1.dsize;
  556.     if (i1 <= (i2+3) * (int)sizeof(short))
  557.         return (0);
  558.     sp[0] += 2;
  559.     sp[++i2] = i1 + item1.dsize;
  560.     bcopy(item.dptr, &buf[i1 + item1.dsize], item.dsize);
  561.     sp[++i2] = i1;
  562.     bcopy(item1.dptr, &buf[i1], item1.dsize);
  563.     return (1);
  564. }
  565.  
  566. #ifdef DEBUG
  567. static
  568. chkblk(buf)
  569.     char buf[PBLKSIZ];
  570. {
  571.     register short *sp;
  572.     register t, i;
  573.  
  574.     sp = (short *)buf;
  575.     t = PBLKSIZ;
  576.     for (i=0; i<sp[0]; i++) {
  577.         if (sp[i+1] > t)
  578.             return (-1);
  579.         t = sp[i+1];
  580.     }
  581.     if (t < (sp[0]+1)*sizeof(short))
  582.         return (-1);
  583.     return (0);
  584. }
  585. #endif
  586. @
  587.  
  588.  
  589. 1.5
  590. log
  591. @Lint.
  592. @
  593. text
  594. @d25 7
  595. @
  596.  
  597.  
  598. 1.4
  599. log
  600. @Lint.
  601. @
  602. text
  603. @d28 1
  604. @
  605.  
  606.  
  607. 1.3
  608. log
  609. @Lint.
  610. @
  611. text
  612. @a23 1
  613. static  long hashinc();
  614. a117 1
  615.     datum item;
  616. @
  617.  
  618.  
  619. 1.2
  620. log
  621. @Lint.
  622. @
  623. text
  624. @d27 1
  625. @
  626.  
  627.  
  628. 1.1
  629. log
  630. @Initial revision
  631. @
  632. text
  633. @d17 2
  634. @
  635.